package com.wc.alorithm.string.trietree;

/**
 * @Author congege
 * @Description
 * @Date Created in 2023/12/2-15:32
 */
public class Trie2 {
    static int N = (int) 1e6 + 10;
    static int[][] son = new int[N][26];
    // 每一个单词数量
    static int[] cnt = new int[N];
    // 单词编码
    static int idx = 0;

    public static void insert(String word) {
        char[] cs = word.toCharArray();
        int p = 0;
        for (char c : cs) {
            if (son[p][c - 'a'] == 0) {
                son[p][c - 'a'] = ++idx;
            }
            p = son[p][c - 'a'];
        }
        ++cnt[p];
    }

    public static boolean query(String word){
        int p = 0;
        char[] cs = word.toCharArray();
        for(char c : cs){
            if (son[p][c - 'a'] == 0){
                return false;
            }
            p = son[p][c - 'a'];
        }

        return cnt[p] != 0;
    }
}
